W10. Singular Value Decomposition

1. Theory

1.1 Introduction and Motivation

Eigenvalue decomposition is one of the most powerful tools in linear algebra, but it has a significant limitation: it applies only to square matrices and, even then, only to diagonalizable ones. Many of the most important matrices in applications — tall data matrices, wide system matrices, rectangular transformations — fall outside this framework entirely. We need a universal factorization that works for any matrix, of any shape and any rank.

There is a second, subtler limitation. Even for symmetric matrices, eigenvalue decomposition gives us a single basis of eigenvectors that simultaneously diagonalizes the matrix in both the domain and the codomain, because for a symmetric matrix the input and output spaces are the same. But for a general rectangular matrix , the domain is and the codomain is — two completely different spaces. We need two orthonormal bases: one for the domain and one for the codomain.

The Spectral Theorem tells us that every real symmetric matrix has an eigendecomposition with orthogonal. This is a beautiful result, but it is special: symmetry is a strong assumption. What we want is something equally clean for arbitrary matrices.

Singular Value Decomposition (SVD) is exactly that universal method. It factors any real matrix as a product of three matrices — an orthogonal matrix, a diagonal matrix, and another orthogonal matrix — capturing the complete geometric and algebraic structure of in a way that eigenvalue decomposition cannot. Every real matrix has an SVD. No condition on shape, rank, or symmetry is required.

1.2 SVD Basics

The fundamental result is:

Theorem (SVD Existence): For every matrix with rank , there exist orthogonal matrices , , and a matrix such that:

The columns of are called the left singular vectors of . They form an orthonormal basis for . The columns of are called the right singular vectors of . They form an orthonormal basis for . The matrix is diagonal — meaning its only non-zero entries are on the main diagonal — with non-negative real values . These diagonal entries are called the singular values of .

To read this decomposition geometrically: the matrix rotates (or reflects) vectors in so that they align with the coordinate axes; then stretches each coordinate axis by the corresponding singular value (and maps from to ); finally rotates (or reflects) in to produce the output. Every linear map can be decomposed into this sequence: rotate–stretch–rotate.

1.2.1 Shape of for Different Matrix Sizes

The matrix has the same shape as — that is, — but all entries outside the main diagonal are zero. Its diagonal entries are the singular values.

• Tall matrix (): looks like a diagonal block stacked on top of an zero block. There are at most singular values.
• Wide matrix (): looks like a diagonal block followed by an zero block to the right. There are at most singular values.
• Square matrix (): is an diagonal matrix.

In all cases, at most singular values can be non-zero, and the rank of equals the number of strictly positive singular values.

1.3 Properties of Singular Values

Singular values have several important properties that make them a robust measure of the “size” and “complexity” of a matrix.

Non-negativity and ordering: By convention, singular values are always listed in non-increasing order: . They are always non-negative real numbers regardless of the entries of .

Rank: The rank of equals the number of non-zero singular values. This gives an efficient way to determine rank by computing the SVD.

Connection to matrix norms: The largest singular value equals the operator (spectral) norm . The Frobenius norm satisfies .

Uniqueness: The singular values of are unique (they depend only on , not on any particular factorization). The singular vectors, however, are not unique when singular values are repeated.

1.4 Computing the SVD

The practical algorithm for computing the SVD relies on a deep connection between and the symmetric matrices and .

1.4.1 Connection to and

Let . Then:

This is exactly the eigendecomposition of : the columns of are the eigenvectors of , and the eigenvalues of are (the squares of the singular values).

Similarly:

So the columns of are the eigenvectors of , and the eigenvalues of are also .

This gives us the key equations:

The right singular vectors are the unit eigenvectors of ; the left singular vectors for are obtained by applying to and normalizing. The remaining columns of (when ) are chosen as any orthonormal basis for the null space of .

1.4.2 Step-by-Step Algorithm

Given :

1. Compute . This is symmetric and positive semi-definite.
2. Find the eigenvalues of . These satisfy because is PSD.
3. Extract singular values: for , where is the number of positive eigenvalues.
4. Find unit eigenvectors of to form the columns of .
5. Compute left singular vectors: for .
6. Extend : complete to a full orthonormal basis of (use the null space of for the remaining vectors).
7. Assemble , , and verify .

1.4.3 Special Cases

Rank-1 matrix: If has rank 1, then (outer product of two unit vectors scaled by a constant). The only non-zero singular value is the norm of the row (or column) — all other singular values are zero.

Symmetric positive semi-definite matrix: If and all eigenvalues , then the SVD coincides with the eigendecomposition: and (the matrix of eigenvectors). Computing the SVD is then simply the same as diagonalizing the matrix.

1.5 Algebraic Properties of the SVD

Given , we can immediately read off the SVD of related matrices:

Transpose: . The roles of and are simply swapped. The singular values remain the same — and always have the same singular values.

Inverse (square, full-rank case): If is and invertible, then:

This is immediate because .

Scalar multiple: For any scalar :

The singular values of are . The singular vectors and are unchanged (they do not depend on scaling). If , the singular values are still non-negative, since the sign can be absorbed into or .

1.6 The Four Fundamental Subspaces via SVD

The SVD provides a complete and elegant description of the four fundamental subspaces of a matrix. This is one of the most important applications of the decomposition.

Recall that for with rank :

• The column space has dimension .
• The left null space has dimension .
• The row space has dimension .
• The null space has dimension .

From the SVD , we read off these subspaces directly:

• : spanned by the first columns of : .
• : spanned by the last columns of : .
• : spanned by the first columns of : .
• : spanned by the last columns of : .

This is the Fundamental Theorem of Linear Algebra: the four subspaces are organized into two orthogonal pairs: in , and in . The columns of form an orthonormal basis for that simultaneously respects both and ; the columns of form an orthonormal basis for that simultaneously respects both and .

Why this works: for , so the first columns of map directly onto independent vectors in . For , , confirming that lie in .

1.7 SVD as a Sum of Rank-1 Matrices

Expanding the product column by column yields a beautiful representation:

Each term is a rank-1 matrix — the outer product of two vectors, scaled by the -th singular value. This decomposition organizes the “information” in by importance: the first term is the most important (it contributes the most to the matrix, since is largest), and successive terms are progressively less significant.

This information hierarchy is the key insight behind low-rank approximation: if we drop the small terms, we get a matrix that is “almost” but has much lower rank — and hence can be stored and processed far more efficiently.

1.8 Applications: Low-Rank Approximation, Image Compression, and Denoising

1.8.1 Frobenius Norm and Energy

The Frobenius norm of a matrix is:

The second equality follows directly from the SVD. The squared Frobenius norm can be thought of as the total energy of the matrix. The fraction of energy captured by the top singular values is:

This ratio is fundamental in deciding how many terms to keep in a low-rank approximation.

1.8.2 The Eckart–Young Theorem

The rank- approximation of is:

This is obtained by keeping only the top terms in the rank-1 expansion and discarding the rest.

Theorem (Eckart–Young, 1936): Among all matrices of rank at most , the best approximation to in the Frobenius norm (and also in the spectral norm) is :

This theorem guarantees that the SVD rank- truncation is optimal — no other rank- matrix gets closer to . The approximation error is precisely the energy of the discarded singular values.

1.8.3 Image Compression

A grayscale image of size pixels is naturally a matrix . Storing the full matrix requires numbers. Using the rank- SVD approximation, we store:

• singular values: numbers
• left singular vectors: numbers
• right singular vectors: numbers

Total storage cost: numbers, compared to for the full matrix. The compression ratio is .

For small , this can achieve dramatic compression while retaining most of the image structure, because natural images tend to have rapidly decaying singular values — most of the energy is concentrated in the first few singular values.

1.8.4 Denoising and PCA

Beyond compression, the SVD is central to Principal Component Analysis (PCA): the right singular vectors (or equivalently, the eigenvectors of ) are the principal components — the directions of maximum variance in the data. Projecting data onto the top- principal components extracts the most informative features.

In denoising, we model a noisy matrix as , where the signal has low rank and the noise is spread across all singular values. Truncating the SVD to the top few singular values removes the noise while preserving the signal.

---

2. Definitions

• Singular Value Decomposition (SVD): A factorization of any real matrix , where and are orthogonal matrices and has non-negative entries only on the main diagonal.
• Left singular vectors: The columns of in the SVD; they form an orthonormal basis of .
• Right singular vectors: The columns of in the SVD; they form an orthonormal basis of .
• Singular values: The non-negative diagonal entries of ; they satisfy .
• Rank (from SVD): The rank of equals the number of strictly positive singular values of .
• Column space : The subspace of spanned by the columns of ; in the SVD, spanned by .
• Null space : The subspace of consisting of all with ; in the SVD, spanned by .
• Row space : The column space of ; equivalently, the subspace of spanned by the rows of ; in the SVD, spanned by .
• Left null space : The null space of ; a subspace of ; in the SVD, spanned by .
• Frobenius norm: ; a measure of the total “size” of a matrix.
• Rank- approximation: The matrix , obtained by keeping only the largest singular value terms in the SVD expansion.
• Eckart–Young theorem: The rank- approximation is the closest matrix of rank at most to in both the Frobenius norm and the spectral norm; the approximation error is .
• Outer product (rank-1 matrix): The matrix formed from column vectors and ; always has rank at most 1.

---

3. Formulas

• SVD factorization: , where , , for , .
• Right singular vectors from : (eigenvectors of ).
• Left singular vectors from right: for .
• SVD of transpose: .
• SVD of inverse (square, invertible): .
• SVD of scalar multiple: ; singular values of are .
• Rank-1 expansion: .
• Best rank- approximation (Eckart–Young): .
• Frobenius approximation error: .
• Frobenius norm via singular values: .
• Storage cost of rank- SVD: numbers.
• Energy fraction of top singular values: .

---

4. Practice

4.1 Compute , Singular Values, and Rank (Lab 8, Task 1)

Let . Compute , find all singular values, determine the rank, and give a geometric interpretation of the action of .

Click to see the solution

Key Concept: We compute , find its eigenvalues, take square roots to get singular values, and then interpret the result geometrically. A zero singular value signals rank deficiency and a collapsed image.

Step 1 — Compute .

Step 2 — Find eigenvalues of .

Since is diagonal, the eigenvalues are read directly:

Step 3 — Extract singular values.

The rank equals the number of strictly positive singular values: .

Step 4 — Geometric interpretation.

Because rank , the matrix collapses the entire plane onto a single line in . Concretely, , so the image is the line spanned by , which in unit-vector form is . The maximum stretch of a unit input vector is . The unit circle is mapped not to an ellipse but to a line segment of length , because the second singular value is zero.

Answer: , singular values , , . Geometrically, collapses the plane onto the line spanned by , stretching by a factor of .

4.2 Compute the Full SVD (Lab 8, Task 2)

Compute the full SVD of .

Click to see the solution

Key Concept: We follow the standard SVD algorithm: compute , diagonalize it to get and , then compute left singular vectors via .

Step 1 — Compute .

Step 2 — Find eigenvalues of .

So and .

Step 3 — Extract singular values.

Step 4 — Find right singular vectors (columns of ).

For : solve .

Take proportional to . Its norm is:

For : is orthogonal to :

Step 5 — Compute left singular vectors.

Similarly, , giving:

Numerically: , , , , , .

Answer: with , , , .

4.3 SVD of and ; Effect of Scaling (Lab 8, Task 3)

Using the SVD of found in Task 4.2: (a) write down the SVD of ; (b) find from the SVD; (c) determine how the singular values change if is replaced by .

Click to see the solution

Key Concept: The SVD formulas , , and let us read off the SVD of related matrices directly from the SVD of , without new computation.

Throughout, , , refer to the SVD of found in Task 4.2, with and .

Part (a) — SVD of .

Step 1: Use the transpose formula. If , then .

Step 2: Since is and square, .

Step 3: Therefore . The left singular vectors of are the columns of (right singular vectors of ), and the right singular vectors of are the columns of (left singular vectors of ). The singular values are the same: and .

Part (b) — SVD of .

Step 1: Since is with both singular values non-zero (), is invertible.

Step 2: Use the inverse formula: , where .

The singular values of are (in decreasing order), approximately and .

Part (c) — Effect of replacing by .

Step 1: Use the scalar multiple formula: .

Step 2: The matrices and are unchanged. The singular values each multiply by :

Answer: (a) (same , roles of and swapped, same singular values). (b) with singular values and . (c) The singular values of are and ; and are unchanged.

4.4 Full SVD and Four Fundamental Subspaces (Lab 8, Task 4)

Let . Compute the full SVD of and identify all four fundamental subspaces.

Click to see the solution

Key Concept: Column 2 of equals column 1, so has rank 1. A rank-1 matrix has exactly one non-zero singular value, and its four fundamental subspaces are each 1-dimensional (or trivial).

Step 1 — Compute .

Step 2 — Find eigenvalues of .

So , .

Step 3 — Extract singular values.

Step 4 — Find right singular vectors (columns of ).

For : . So , normalized:

For : is orthogonal to :

Step 5 — Compute left singular vectors.

For : choose any unit vector orthogonal to in :

Step 6 — Assemble SVD.

Step 7 — Four fundamental subspaces.

Answer: , , rank . , , .

4.5 SVD of a Symmetric PSD Matrix (Lab 8, Task 5)

Let be a symmetric positive semi-definite matrix with eigenvalues and corresponding orthonormal eigenvectors . Write down the SVD of , identify all four fundamental subspaces, and explain why this case is simpler than the general SVD.

Click to see the solution

Key Concept: For a symmetric positive semi-definite (PSD) matrix, the eigendecomposition is already the SVD, because and the singular values equal the eigenvalues. No separate computation of is required.

Step 1 — Eigendecomposition.

Let be the matrix of orthonormal eigenvectors and . Since is symmetric PSD:

Step 2 — Write the SVD.

Comparing with : set and .

Step 3 — Rank.

The number of non-zero singular values is 2, so .

Step 4 — Four fundamental subspaces.

Since is symmetric, and .

• (dimension 2)
• (dimension 1)

Step 5 — Why this case is simpler.

In the general SVD algorithm, we must: (i) compute (a separate matrix product), (ii) find its eigenvectors to form , (iii) separately compute each , and (iv) extend using the null space of . For a symmetric PSD matrix, steps (iii) and (iv) are automatic because . Furthermore, , so the eigenvectors of are the same as those of — no new computation is needed. The SVD reduces entirely to the eigendecomposition, which we already know how to perform.

Answer: SVD is ; , , ; rank ; ; . The simplification is that , so the SVD is identical to the eigendecomposition.

4.6 Best Rank-1 and Rank-2 Approximations (Lab 8, Task 6)

Suppose is already given in its SVD rank-1 expansion. Find the best rank-1 approximation , the best rank-2 approximation , and compute the Frobenius errors and .

Click to see the solution

Key Concept: By the Eckart–Young theorem, the best rank- approximation is obtained by keeping the largest singular value terms in the SVD expansion. The Frobenius error equals the square root of the sum of squares of the discarded singular values.

The singular values are , , (decreasing order, as required for SVD).

Step 1 — Best rank-1 approximation .

Keep only the term with the largest singular value:

Step 2 — Best rank-2 approximation .

Keep the two largest terms:

Step 3 — Frobenius error .

By Eckart–Young, the discarded singular values are and :

Step 4 — Frobenius error .

Only is discarded:

Step 5 — Interpretation.

The rank-1 approximation retains of total energy. The rank-2 approximation retains of total energy. Adding the second singular-value term reduces the error from to .

Answer: , ; ; .

4.7 Energy Retention and Storage Comparison (Lab 8, Task 7)

A matrix has singular values , , , , and all remaining singular values are zero. Find the smallest such that the rank- approximation retains at least of the total energy. Compare the storage cost of the rank- approximation with the storage cost of the full matrix.

Click to see the solution

Key Concept: The energy fraction captured by the top singular values is . We find the smallest for which this fraction reaches , then compare storage costs.

Step 1 — Compute total energy.

Step 2 — Check .

Step 3 — Check .

The smallest that retains at least of total energy is .

Step 4 — Compare storage costs.

• Full matrix: numbers.
• Rank-2 SVD: we store left singular vectors ( numbers), right singular vectors ( numbers), and singular values ( numbers). Total: numbers.
• Compression ratio: .

The rank-2 SVD requires less than of the storage of the full matrix while capturing over of the energy.

Step 5 — Other applications of this technique.

Beyond image compression, this approach is used in: recommendation systems (matrix factorization for collaborative filtering), natural language processing (latent semantic analysis), network analysis (compressing adjacency matrices), and any machine learning pipeline where the data matrix has low effective rank.

Answer: (energy fraction ). Storage: numbers vs.  for the full matrix — a compression ratio of .

4.8 Full SVD and Best Rank-1 Approximation (Lab 8, Task 8)

Let . Compute the full SVD, identify all four fundamental subspaces, and write down the best rank-1 approximation .

Click to see the solution

Key Concept: For a matrix of rank 2, is and has one zero eigenvalue. We find all three eigenvectors of , then compute from the two non-zero singular pairs, and finally form using the dominant term.

Step 1 — Compute ().

Step 2 — Find eigenvalues of .

Eigenvalues: , , . Thus , , , and .

Step 3 — Find right singular vectors (columns of ).

For : gives the system , , . From row-reduction: and , so .

For : : and , so .

For : null space of : , , so .

Step 4 — Compute left singular vectors.

Step 5 — Assemble SVD.

Step 6 — Four fundamental subspaces.

• (full, dimension 2)
• (dimension 0, since )
• (dimension 2)
• (dimension 1)

Step 7 — Best rank-1 approximation.

Answer: , , , rank . The best rank-1 approximation is .

4.9 Singular Values and Rank for Three Matrices (Assignment 8, Problem 1)

Compute the singular values and determine the rank of each of the following matrices: (a) , (b) , (c) .

Click to see the solution

Key Concept: The singular values of are the square roots of the eigenvalues of . For diagonal or rank-deficient matrices these computations simplify considerably: diagonal entries give singular values directly (as absolute values), and rank-deficient matrices always have at least one zero singular value.

Part (a) — .

Step 1: (diagonal, so eigenvalues are , ).

Step 2: , . Note that singular values are always non-negative, even though .

Step 3: Both singular values are positive, so .

Part (b) — .

Step 1: Observe that row 2 row 1, so .

Step 2: .

Step 3: , giving , .

Step 4: , . .

Part (c) — .

Step 1: . All eigenvalues are .

Step 2: . .

Answer: (a) , , rank . (b) , , rank . (c) , rank .

4.10 Full SVD of a Matrix (Assignment 8, Problem 2)

Compute the full SVD of .

Click to see the solution

Key Concept: is a tall () matrix with diagonal non-zero entries. Because is diagonal, the computation is straightforward. We must extend to a full orthogonal matrix by adding a third column spanning the null space of .

Step 1 — Compute ().

Step 2 — Eigenvalues and singular values.

, so , . Thus , , rank .

Step 3 — Right singular vectors (columns of ).

Eigenvector for : . Eigenvector for : .

Step 4 — Left singular vectors.

Step 5 — Extend to .

We need orthogonal to both and . The only such unit vector is:

Step 6 — Assemble and verify.

Verification: , then . ✓

Answer: , , ; singular values , , rank .

4.11 Reduced SVD of a Tall Matrix (Assignment 8, Problem 3)

Compute the reduced (thin) SVD of .

Click to see the solution

Key Concept: The reduced (thin) SVD keeps only the non-zero singular triplets: where is , is diagonal, and is . For this matrix with rank 2, the reduced SVD has the same but has only 2 columns (no third extension column needed).

Step 1 — Compute ().

Step 2 — Eigenvalues and singular values.

, so , . Thus , , rank .

Step 3 — Right singular vectors (columns of ).

Eigenvector for : . Eigenvector for : .

Step 4 — Left singular vectors (columns of ).

Step 5 — Assemble reduced SVD.

Verification: , then . ✓

Answer: Reduced SVD: , , ; singular values , .

4.12 SVD of a Rank-Deficient Matrix (Assignment 8, Problem 4)

Find the singular values, rank, and full SVD of .

Click to see the solution

Key Concept: Both rows of are identical, so has rank 1. There will be exactly one non-zero singular value. The SVD must be extended to a full orthogonal by choosing a vector orthogonal to .

Step 1 — Compute .

Step 2 — Eigenvalues and singular values.

. So , , giving , , rank .

Step 3 — Right singular vectors.

For : . So .

For : orthogonal complement: .

Step 4 — Left singular vectors.

For : orthogonal to : .

Step 5 — Assemble and verify.

Verification: . ✓

Answer: , , rank . , .

4.13 SVD of a Wide Matrix (Assignment 8, Problem 5)

Find the singular values, rank, and full SVD of .

Click to see the solution

Key Concept: is a wide matrix. Its is and diagonal (since itself is essentially diagonal with a trailing zero column). We must extend to a full orthogonal matrix by including the null-space vector.

Step 1 — Compute ().

Step 2 — Eigenvalues and singular values.

, so , , . Thus , , , rank .

Step 3 — Right singular vectors (columns of ).

Eigenvectors of (read off directly since it is diagonal):

(for ), (for ), (for ).

Step 4 — Left singular vectors.

Step 5 — Assemble SVD.

Verification: . ✓

Answer: , , , rank . , , .

4.14 True/False: SVD Properties (Assignment 8, Problem 6)

Determine whether each statement is true or false. Justify your answer.

1. Every square matrix has a unique SVD.

2. The singular values of are always non-negative.

3. If is symmetric positive definite, then its singular values equal its eigenvalues.

4. The rank of a matrix equals the number of non-zero singular values.

Click to see the solution

Key Concept: These questions test the core properties of singular values and the SVD. Remember: singular values are unique, but singular vectors (and hence the full factorization , ) are not.

Part (a) — “Every square matrix has a unique SVD.” — FALSE.

Step 1: Every matrix (square or not) does have an SVD, so existence is true.

Step 2: However, uniqueness fails. The singular values are unique (they are determined by the eigenvalues of ), but the singular vectors are not. For example, if (repeated singular values), any rotation in the corresponding eigenspace of yields another valid set of right singular vectors, and correspondingly another valid . Even for distinct singular values, changing the sign of and compensating in gives a different but valid SVD.

Conclusion: The SVD exists for every matrix but is not unique in general.

Part (b) — “The singular values of are always non-negative.” — TRUE.

Step 1: Singular values are defined as .

Step 2: The matrix is symmetric positive semi-definite: for any vector , . Therefore all eigenvalues of are .

Step 3: The square root of a non-negative number is non-negative, so always.

Part (c) — “If is symmetric positive definite, then its singular values equal its eigenvalues.” — TRUE.

Step 1: If is symmetric positive definite (SPD), then where with all .

Step 2: For a symmetric matrix, . The eigenvalues of are .

Step 3: Therefore (since all for SPD).

Conclusion: The singular values and eigenvalues coincide for symmetric positive definite matrices.

Part (d) — “The rank of a matrix equals the number of non-zero singular values.” — TRUE.

Step 1: The rank of equals the dimension of its column space , which by the SVD equals the number of non-zero singular values (those contribute independent columns to ).

Step 2: Formally: and the zero singular values correspond to terms that vanish in the sum , confirming rank equals the number of non-zero .

Answer: (a) False — singular values are unique but singular vectors are not, so the full SVD factorization is not unique. (b) True — singular values are square roots of eigenvalues of the PSD matrix . (c) True — for SPD , . (d) True — rank equals the number of strictly positive singular values.

4.15 SVD of a Symmetric Matrix (Assignment 8, Problem 7)

Compute the SVD of .

Click to see the solution

Key Concept: is a symmetric matrix, so its eigendecomposition gives the SVD directly: (the eigenvector matrix) and the singular values are the (positive) eigenvalues. This simplifies the computation significantly.

Step 1 — Compute .

Since , we have . But it is easier to diagonalize directly.

Step 2 — Eigenvalues of .

So , . Both are positive, confirming is SPD.

Step 3 — Singular values.

Step 4 — Eigenvectors of (= right and left singular vectors).

For : . So .

For : . So .

Step 5 — Verify using .

Step 6 — Assemble SVD.

Verification: . ✓

Answer: , . , .

4.16 Rank and SVD from Known Singular Values (Assignment 8, Problem 8)

A matrix has singular values , , . (a) What is the rank of ? (b) Write the SVD of in terms of the singular vectors of . (c) What are the singular values of ?

Click to see the solution

Key Concept: Given the SVD , we can immediately read off properties of and using the algebraic SVD formulas, without knowing , , or the shape of explicitly.

Part (a) — Rank of .

Step 1: The rank of equals the number of strictly positive singular values.

Step 2: We have , , . Two singular values are positive.

Part (b) — SVD of .

Step 1: If , then by the transpose formula:

Step 2: is the transpose of ; for a square diagonal , we have .

Step 3: Therefore . The left singular vectors of are the columns of (the right singular vectors of ), and the right singular vectors of are the columns of (the left singular vectors of ).

Step 4: The singular values of are the same as those of : , , .

Part (c) — Singular values of .

Step 1: Use the scalar multiple formula: .

Step 2: and are unchanged. The singular values multiply by :

Answer: (a) Rank . (b) with the same singular values ; the roles of and are swapped. (c) The singular values of are .

4.17 Compute and SVD for a Nilpotent Matrix (Assignment 8, Problem 9)

Let . Compute , find the singular values, and determine the full SVD.

Click to see the solution

Key Concept: is a nilpotent matrix (), so it is not diagonalizable by eigendecomposition. Nevertheless, the SVD exists for every matrix. Because is diagonal, the computation is straightforward.

Step 1 — Compute .

Step 2 — Eigenvalues and singular values.

, so , . Thus:

Note: has eigenvalues (nilpotent), but singular value . Singular values and eigenvalues are completely different objects.

Step 3 — Right singular vectors (columns of ).

Eigenvector of for : gives , so . Thus .

Eigenvector for : gives . Thus .

Step 4 — Left singular vectors.

For : orthogonal to in : .

Step 5 — Assemble and verify.

Verification: . ✓

Answer: ; , , rank . Full SVD: , , .

4.18 SVD of a Diagonal Matrix (Tutorial 8, Example 1)

Compute the full SVD of .

Click to see the solution

Key Concept: For a diagonal matrix, is also diagonal, making the eigenvalue computation trivial. We follow the standard algorithm: find from , extract , then compute .

Step 1 — Compute .

Step 2 — Find eigenvalues of .

Since is already diagonal, the eigenvalues are read directly: , .

We list them in decreasing order: .

Step 3 — Extract singular values.

So .

Step 4 — Find right singular vectors (columns of ).

The eigenvector corresponding to is the standard basis vector (since ). The eigenvector for is .

Note: .

Step 5 — Compute left singular vectors.

Step 6 — Assemble and verify.

Verification: . ✓

Answer: , with singular values , .

4.19 Rank and Subspace Dimensions from Singular Values (Tutorial 8, Example 2)

A matrix has singular values (and one zero singular value). Determine the rank and the dimensions of all four fundamental subspaces.

Click to see the solution

Key Concept: The rank equals the number of non-zero singular values. The dimensions of all four fundamental subspaces follow from the rank-nullity theorem.

Step 1 — Determine the rank.

There are three non-zero singular values (), so:

Step 2 — Find subspace dimensions.

The matrix is , so and .

• (column space, subspace of ): .
• (left null space, subspace of ): .
• (row space, subspace of ): .
• (null space, subspace of ): .

Interpretation: The SVD provides explicit orthonormal bases for all four subspaces: span ; span ; span ; and spans .

Answer: Rank ; , , , .

4.20 SVD of a Rank-1 Matrix (Tutorial 8, Example 3)

Compute the SVD of .

Click to see the solution

Key Concept: This matrix has rank 1 because each row is a scalar multiple of . The SVD of a rank-1 matrix has exactly one non-zero singular value. We follow the standard algorithm, then extend and to full orthogonal matrices.

Step 1 — Compute .

Step 2 — Find eigenvalues of .

So , .

Step 3 — Extract singular values.

Only one non-zero singular value, confirming rank 1.

Step 4 — Find right singular vectors.

For : solve :

For : the null space of is orthogonal to :

(Check: . ✓)

Step 5 — Compute the first left singular vector.

Step 6 — Extend to a full orthonormal basis of .

We need orthogonal to and to each other. One valid choice (Gram–Schmidt or inspection):

(These form an orthonormal set together with .)

Step 7 — Assemble the SVD.

Answer: , ; rank . The reduced SVD is .

4.21 Four Fundamental Subspaces from SVD (Tutorial 8, Example 4)

A matrix has SVD with (as a matrix) and orthonormal left singular vectors and right singular vectors . Identify all four fundamental subspaces.

Click to see the solution

Key Concept: Given the SVD, the four fundamental subspaces are read directly from the singular vectors and the rank. No further computation is needed.

Step 1 — Determine the rank.

The diagonal of is . There are three non-zero singular values, so:

Step 2 — Read off the four fundamental subspaces.

The matrix is , so , .

• Column space , : Spanned by — the left singular vectors corresponding to the non-zero singular values.
• Left null space , : Spanned by — the left singular vector corresponding to .
• Row space , : Spanned by — the right singular vectors corresponding to the non-zero singular values.
• Null space , : Spanned by — the right singular vectors corresponding to the zero singular values.

Verification of dimensions: ✓ and ✓.

Orthogonality: in (since is orthogonal) and in (since is orthogonal). This is the Fundamental Theorem of Linear Algebra.

Answer: ; ; ; .

4.22 SVD as a Sum of Rank-1 Matrices (Tutorial 8, Example 5)

Compute the full SVD of and express as a sum of rank-1 matrices.

Click to see the solution

Key Concept: Once we have the SVD, the rank-1 expansion is immediate. We verify the expansion by showing the sum reconstructs .

Step 1 — Compute .

Step 2 — Eigenvalues and singular values.

is diagonal, so , .

Both are positive, so rank .

Step 3 — Right singular vectors.

Step 4 — Left singular vectors.

Extend to : We need orthogonal to both and . The only unit vector in orthogonal to both is:

Step 5 — Write the SVD.

Step 6 — Rank-1 expansion.

Answer: , ; .

4.23 Prove the Eigenvalue Connection (Tutorial 8, Example 6)

Let be the SVD of . Prove that and deduce that the eigenvalues of are .

Click to see the solution

Key Concept: This proof directly establishes the connection between SVD and eigendecomposition, showing why is the right matrix to compute when finding singular values. The key tools are the transpose of a product and the orthogonality .

Step 1 — Expand using the SVD.

Using the property :

Therefore:

Step 2 — Simplify using .

Since is orthogonal, . Thus:

Step 3 — Interpret as eigendecomposition.

The matrix is diagonal: if has diagonal entries (and zeros elsewhere), then is the diagonal matrix .

The expression is exactly the eigendecomposition of : it is in the form with orthogonal and diagonal.

Conclusion: The eigenvalues of are the diagonal entries of , which are . In particular, all eigenvalues of are non-negative — which confirms that is positive semi-definite for any matrix .

Answer: ; eigenvalues of are .

4.24 Image Compression via SVD (Tutorial 8, Example 7)

A grayscale image is represented as a matrix . Suppose the rank of is (all singular values are non-zero). (a) How much storage does the full matrix require? (b) Compute the storage cost for the rank-3 SVD approximation. (c) What is the compression ratio?

Click to see the solution

Key Concept: The rank- SVD approximation stores left singular vectors (each of length ), right singular vectors (each of length ), and singular values — a total of numbers, which can be dramatically less than the entries of the full matrix.

Step 1 — Full matrix storage.

Step 2 — Rank-3 approximation storage.

For , , :

Breaking this down:

• Singular values: numbers
• Left singular vectors: numbers
• Right singular vectors: numbers
• Total: numbers ✓

Step 3 — Compression ratio.

The rank-3 approximation uses only about of the storage of the full matrix. Whether this approximation is visually acceptable depends on how much energy the top 3 singular values capture — if the image has strong low-rank structure (e.g., smooth backgrounds), the approximation may look quite good.

Answer: Full storage: ; rank-3 storage: ; compression ratio .